'''
https://leetcode.cn/problems/similar-string-groups/description/
'''
from typing import List


class UnionFindSet:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.sets = n
    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]
    def is_same_set(self, i, j):
        return self.find(i) == self.find(j)
    def union(self, i, j):
        x, y = self.find(i), self.find(j)
        if x != y:
            self.father[x] = y
            self.sets -= 1

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        m, n = len(strs), len(strs[0])

        def is_similar(s1, s2):
            c = 0
            for i in range(n):
                if s1[i] != s2[i]:
                    c += 1
                if c >= 3: return False
            return True

        ufs = UnionFindSet(m)
        for i in range(m):
            for j in range(i + 1, m):
                if not ufs.is_same_set(i, j) and is_similar(strs[i], strs[j]):
                    ufs.union(i, j)
        return ufs.sets